#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define MAX_TASKS 100  // 最大任务数量

// 定义资源池结构体
typedef struct
{
    int total_cpu;        // 总 CPU 时间
    int total_memory;     // 总内存
    int available_cpu;    // 可用 CPU 时间
    int available_memory; // 可用内存
    pthread_mutex_t lock; // 保护资源池的互斥锁
} ResourcePool;

// 定义任务结构体
typedef struct
{
    int task_id;          // 任务 ID
    int cpu_needed;       // 任务所需的 CPU 时间
    int memory_needed;    // 任务所需的内存
    int priority;         // 任务优先级，值越小优先级越高
} Task;

// 定义优先级队列（使用最小堆实现）
typedef struct
{
    Task *tasks[MAX_TASKS]; // 存储任务的数组
    int size;               // 队列的大小
} PriorityQueue;

// 模拟资源池
ResourcePool resource_pool;
PriorityQueue pq;

// 初始化资源池
void init_resource_pool(int cpu, int memory)
{
    resource_pool.total_cpu = cpu;
    resource_pool.total_memory = memory;
    resource_pool.available_cpu = cpu;
    resource_pool.available_memory = memory;
    pthread_mutex_init(&resource_pool.lock, NULL);
}

// 初始化优先级队列
void init_priority_queue()
{
    pq.size = 0;
}

// 向优先级队列中插入任务
void enqueue(PriorityQueue *pq, Task *task)
{
    if (pq->size < MAX_TASKS)
    {
        pq->tasks[pq->size] = task;
        int i = pq->size;
        pq->size++;
        // 调整堆结构，确保优先级顺序
        while (i > 0 && pq->tasks[(i - 1) / 2]->priority > pq->tasks[i]->priority)
        {
            Task *temp = pq->tasks[i];
            pq->tasks[i] = pq->tasks[(i - 1) / 2];
            pq->tasks[(i - 1) / 2] = temp;
            i = (i - 1) / 2;
        }
    }
}

// 弹出优先级最高的任务（堆顶）
Task *dequeue(PriorityQueue *pq)
{
    if (pq->size == 0) return NULL;

    Task *highest_priority_task = pq->tasks[0];
    pq->size--;
    pq->tasks[0] = pq->tasks[pq->size]; // 将堆尾的任务移到堆顶

    int i = 0;
    // 调整堆结构，确保堆顶是优先级最高的任务
    while (2 * i + 1 < pq->size)
    {
        int left_child = 2 * i + 1;
        int right_child = 2 * i + 2;
        int smallest = i;

        if (left_child < pq->size && pq->tasks[left_child]->priority < pq->tasks[smallest]->priority)
            smallest = left_child;
        if (right_child < pq->size && pq->tasks[right_child]->priority < pq->tasks[smallest]->priority)
            smallest = right_child;
        if (smallest != i)
        {
            Task *temp = pq->tasks[i];
            pq->tasks[i] = pq->tasks[smallest];
            pq->tasks[smallest] = temp;
            i = smallest;
        }
        else
        {
            break;
        }
    }

    return highest_priority_task;
}

// 分配资源
int allocate_resources(Task *task)
{
    pthread_mutex_lock(&resource_pool.lock);

    // 检查资源是否足够
    if (task->cpu_needed <= resource_pool.available_cpu && task->memory_needed <= resource_pool.available_memory)
    {
        resource_pool.available_cpu -= task->cpu_needed;
        resource_pool.available_memory -= task->memory_needed;
        pthread_mutex_unlock(&resource_pool.lock);
        return 1; // 分配成功
    }
    else
    {
        pthread_mutex_unlock(&resource_pool.lock);
        return 0; // 分配失败
    }
}

// 释放资源
void release_resources(Task *task)
{
    pthread_mutex_lock(&resource_pool.lock);
    resource_pool.available_cpu += task->cpu_needed;
    resource_pool.available_memory += task->memory_needed;
    pthread_mutex_unlock(&resource_pool.lock);
}

// 模拟任务执行
void *task_execution(void *arg)
{
    Task *task = (Task *) arg;

    printf("Task %d is waiting for resources...\n", task->task_id);

    // 等待资源分配
    while (!allocate_resources(task))
    {
        // 如果资源不足，任务就继续等待
    }

    printf("Task %d is running...\n", task->task_id);
    sleep(4); // 模拟任务执行

    // 执行完毕后释放资源
    release_resources(task);
    printf("Task %d has finished and released resources.\n", task->task_id);

    free(task); // 释放任务内存
    return NULL;
}

// 调度任务
void schedule_tasks()
{
    pthread_t threads[MAX_TASKS];
    while (pq.size > 0)
    {
        // 取出优先级最高的任务
        Task *task = dequeue(&pq);
        if (task != NULL)
        {
            // 创建线程执行任务
            pthread_create(&threads[task->task_id], NULL, task_execution, (void *) task);
        }
    }

    // 等待所有线程执行完成
    for (int i = 0; i < MAX_TASKS; i++)
    {
        pthread_join(threads[i], NULL);
    }
}

int main()
{
    init_resource_pool(10, 20); // 初始化资源池
    init_priority_queue();       // 初始化优先级队列

    // 向队列中添加任务
    for (int i = 0; i < 5; i++)
    {
        Task *task = (Task *) malloc(sizeof(Task));
        task->task_id = i;
        task->cpu_needed = 2 + i;
        task->memory_needed = 4 + i;
        task->priority = 5 - i;  // 设置任务的优先级，优先级越高值越小

        enqueue(&pq, task);  // 将任务插入优先级队列
    }

    // 调度并执行任务
    schedule_tasks();

    return 0;
}

